class PPT

Definition

$\mathbf{PPT}$ or $\mathbf{PP}$ is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with error probability less than $1/2$ for all instances.

Notes

• $\mathbf{PP}$ includes BPP
• $\mathbf{PP}$ included in PSPACE

See also

• P
• BPP
• PH
  • Toda's theorem

References

1. https://en.wikipedia.org/wiki/PP_(complexity)
2. S. Toda, “PP is as Hard as the Polynomial-Time Hierarchy,” SIAM J. Comput., vol. 20, no. 5, pp. 865–877, Oct. 1991, doi: 10.1137/0220053.
3. https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture3.pdf